package com.beikai.demo01.sort.impl;

import com.beikai.demo01.sort.ArrSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @author : hanbeikai
 * Date: 2021/6/4 7:49 下午
 * Description: 插入排序
 * 首先 遍历数组,查询到要比较的元素下标
 * 与这个元素之前的元素进行比较,如果有大于当前位置的元素,则向后移一位,空出的位置最后由当前元素替换
 */
public class ChaRuSort extends ArrSort {


    @Override
    public int[] sort(int[] arr) {

        // 遍历数组元素
        for (int i = 1; i < arr.length; i++) {
            // 当前元素
            int tempArr = arr[i];
            // 当前临时坐标
            int tempIndex = i;
            // 与之前的元素进行比较
            while (tempIndex > 0) {
                // 如果当前坐标左边的数小于当前坐标的值,则说明左边所有的值都小于当前值,则直接跳出
                if (arr[tempIndex - 1] >= tempArr) {
                    break;
                }

                arr[tempIndex] = arr[tempIndex -1];
                tempIndex--;
            }

            if (tempIndex != i){
                arr[tempIndex] = tempArr;
            }
        }

        return arr;
    }
}
